package ru.susu.algebra.field.quadratic;

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Date;
import java.util.List;
import java.util.Map;

import org.apache.log4j.Logger;

import com.google.common.collect.Maps;

import ru.susu.algebra.operation.IOperation;
import ru.susu.algebra.operation.OperationFacade;
import ru.susu.algebra.pair.Pair;
import ru.susu.algebra.util.LRUHashMap;

/**
 * Строится рекуррентная последовательность на основе основной единицы квадратичного поля.
 * c = tr(a+bw)=2a+b, d = Norm(a+bw)
 *
 *  an2 = c*an1 - d*an0, a0 = 1, a1 = a,
 *  bn2 = c*bn1 - d*bn0, b0 = 0, b1 = b.
 *
 *  Все элементы берутся по модулю и ищется период данной последовательности.
 *
 * @author akargapolov
 * @since: 22.04.2010
 */
public class GeneralUnitRecursivePeriodExtractor implements IOperation<List<Pair<BigInteger, BigInteger>>>
{
	private static final Logger _log = Logger.getLogger("PeriodExtractor");

	public static final GeneralUnitRecursivePeriodExtractor instance = new GeneralUnitRecursivePeriodExtractor();


	/**
	 * Массив исходных данных содержит три элемента:
	 * sources[0] - основная единица поля {@link QuadraticFieldGeneralForm}
	 * sources[1] - модуль по которому происходят вычисления {@link BigInteger}
	 * sources[2] - необязательный логический параметр, признак необходимости вести лог
	 * @param sources исходные данные для операции
	 * @return список элементов последовательности, до первой периодичности
	 */
	@Override
	public List<Pair<BigInteger, BigInteger>> performOperation(Object... sources)
	{
		Date start = new Date();
		QuadraticFieldGeneralForm unit = (QuadraticFieldGeneralForm)sources[0];
		BigInteger mod = (BigInteger)sources[1];
		Boolean debug = (Boolean)OperationFacade.getSourceSafe(2, false, sources);
		BigInteger c;
		BigInteger d;

		try
		{
			c = unit.getTrace();
			d = unit.norm();
			_log.info("c = " + c + "; d = " + d);
		}
		catch (Exception e)
		{
			throw new RuntimeException(e);
		}

		Map<Pair<?, ?>,Integer> indexMap = Maps.newHashMap();
		List<Pair<BigInteger, BigInteger>> list = initializeList(unit, mod, debug, indexMap);
		int index = list.size() - 1;
		List<Integer> goodIndexes = new ArrayList<Integer>();

		while (1 == 1)
		{
			BigInteger a0 = list.get(index-1).getKey();
			BigInteger a1 = list.get(index).getKey();
			BigInteger b0 = list.get(index-1).getValue();
			BigInteger b1 = list.get(index).getValue();
			BigInteger a2 = c.multiply(a1).subtract(d.multiply(a0)).mod(mod);
			BigInteger b2 = c.multiply(b1).subtract(d.multiply(b0)).mod(mod);
			Pair<BigInteger, BigInteger> pair1 = Pair.pair(a1, b1);
			Pair<BigInteger, BigInteger> pair2 = Pair.pair(a2, b2);
			BigInteger mod7 = pair2.getKey().add(pair2.getValue().multiply(BigInteger.valueOf(8))).mod(mod);
			if (mod7.equals(BigInteger.valueOf(1)))
			{
				goodIndexes.add(index + 1);
			}
			if (debug)
			{
				System.out.println((index + 1) + ": " + pair2 + " " + mod7);
			}
			Pair<?,?> pairPair = Pair.pair(pair1, pair2);
			if (indexMap.containsKey(pairPair))
			{
				_log.info("Period - " + new Pair<Integer, Integer>(index, indexMap.get(pairPair)));
				_log.info("Good indexes: " + Arrays.toString(goodIndexes.toArray()));
				_log.info("Time - " + (new Date().getTime() - start.getTime()) + "ms");
				//return index - indexMap.get(pairPair);
				list.add(pair2);
				return list;
			}
			indexMap.put(pairPair, index);
			list.add(pair2);
			index++;
		}
	}

	/**
	 * Инициализация списка элементов последовательности: заносятся 0й и 1й элементы в список, также они заносятся в мап индексов.
	 * @param unit основная единица
	 * @param mod модуль
	 * @param indexMap мап индексов для быстрого поиска совпадений
	 * @return проинициализированный список
	 */
	protected List<Pair<BigInteger, BigInteger>> initializeList(QuadraticFieldGeneralForm unit, BigInteger mod, Boolean debug, Map<Pair<?,?>, Integer> indexMap)
	{
		List<Pair<BigInteger, BigInteger>> result = new ArrayList<Pair<BigInteger, BigInteger>>();
		Pair<BigInteger, BigInteger> a0 = new Pair<BigInteger, BigInteger>(BigInteger.ONE, BigInteger.ZERO);
		Pair<BigInteger, BigInteger> a1 = new Pair<BigInteger, BigInteger>(unit.getA().mod(mod), unit.getB().mod(mod));
		result.add(a0);
		result.add(a1);
		indexMap.put(new Pair<Pair<BigInteger, BigInteger>, Pair<BigInteger, BigInteger>>(a0, a1), 0);
		if (debug)
		{
			System.out.println(a0);
			System.out.println(a1);
		}
		return result;
	}
}
